package data

import (
	"fmt"
	"math"
	"math/rand"
	"sync"
	"time"
)

const (
	// DefaultMaxLevel is a reasonable default maximum height for the skip list.
	// Adjust based on expected number of elements (log_1/p(N)).
	DefaultMaxLevel = 32
	// DefaultProbability is the default probability factor for level generation.
	// Common values are 0.5 or 0.25.
	DefaultProbability = 0.5
)

// Node represents an element within the skip list.
type Node struct {
	// key is used for ordering (like a score).
	key float64
	// value holds the associated data.
	value any
	// forward pointers to the next node at each level.
	// forward[0] is the base level pointer.
	forward []*Node
}

// newNode creates a new skip list node.
func newNode(level int, key float64, value any) *Node {
	return &Node{
		key:     key,
		value:   value,
		forward: make([]*Node, level), // level determines the height/number of forward pointers
	}
}

// SkipList represents the skip list data structure.
type SkipList struct {
	// head is the sentinel node, pointing to the beginning of the list at all levels.
	head *Node
	// level is the current highest level present in the list (1-based).
	level int
	// maxLevel is the maximum allowed level for any node.
	maxLevel int
	// p is the probability factor used for random level generation.
	p float64
	// randSource provides the source of randomness.
	randSource rand.Source
	// length is the number of elements in the skip list (excluding the head).
	length int
	// Mutex for concurrent access safety. RWMutex allows multiple readers.
	mutex sync.RWMutex
}

// NewSkipList creates a new, empty skip list.
func NewSkipList(maxLevel int, p float64) *SkipList {
	if maxLevel <= 0 {
		maxLevel = DefaultMaxLevel
	}
	if p <= 0 || p >= 1 {
		p = DefaultProbability
	}
	// Initialize head node with minimum possible key and maxLevel forward pointers
	head := newNode(maxLevel, math.Inf(-1), nil)

	return &SkipList{
		head:       head,
		level:      1, // Start with only the base level active
		maxLevel:   maxLevel,
		p:          p,
		randSource: rand.NewSource(time.Now().UnixNano()), // Seed random source
		length:     0,
	}
}

// NewDefaultSkipList creates a skip list with default parameters.
func NewDefaultSkipList() *SkipList {
	return NewSkipList(DefaultMaxLevel, DefaultProbability)
}

// randomLevel determines the level for a new node based on probability p.
// Returns the number of levels the node should span (1 to maxLevel).
func (sl *SkipList) randomLevel() int {
	level := 1
	// Use the seeded random source
	r := rand.New(sl.randSource)
	for r.Float64() < sl.p && level < sl.maxLevel {
		level++
	}
	return level
}

// Search finds the value associated with a given key.
// Returns the value and true if found, otherwise nil and false.
func (sl *SkipList) Search(key float64) (value any, ok bool) {
	sl.mutex.RLock() // Read lock for searching
	defer sl.mutex.RUnlock()

	node := sl.head
	// Iterate down from the highest current level
	for i := sl.level - 1; i >= 0; i-- {
		// Traverse forward at the current level
		for node.forward[i] != nil && node.forward[i].key < key {
			node = node.forward[i]
		}
	}

	// After the loops, node is the predecessor of the potential target node at level 0.
	// Move to the candidate node at the base level.
	node = node.forward[0]

	// Check if the candidate node exists and its key matches
	if node != nil && node.key == key {
		return node.value, true
	}

	// Not found
	return nil, false
}

func (sl *SkipList) FindRange(start, end float64) (values []*Node) {
	sl.mutex.RLock() // Read lock for searching
	defer sl.mutex.RUnlock()
	node := sl.head
	// Iterate down from the highest current level
	for i := sl.level - 1; i >= 0; i-- {
		// Traverse forward at the current level
		for node.forward[i] != nil && node.forward[i].key < start {
			node = node.forward[i]
		}
	}

	node = node.forward[0]
	for node != nil && node.key <= end {
		values = append(values, node)
		node = node.forward[0]
	}
	return values
}

// Insert adds a new key-value pair or updates the value if the key already exists.
func (sl *SkipList) Insert(key float64, value any) {
	sl.mutex.Lock() // Full lock for insertion
	defer sl.mutex.Unlock()

	// update slice stores pointers to the nodes that need their forward pointers updated.
	update := make([]*Node, sl.maxLevel)
	node := sl.head

	// Find insertion points at each level (find predecessors)
	for i := sl.level - 1; i >= 0; i-- {
		for node.forward[i] != nil && node.forward[i].key < key {
			node = node.forward[i]
		}
		update[i] = node // Store predecessor at level i
	}

	// Candidate node at base level
	node = node.forward[0]

	// If key already exists, update the value and return
	if node != nil && node.key == key {
		node.value = value
		return
	}

	// Key doesn't exist, proceed with insertion
	newNodeLevel := sl.randomLevel()

	// If the new node's level is higher than the current list level,
	// update the list's level and initialize new levels in 'update' slice
	// to point from the head.
	if newNodeLevel > sl.level {
		for i := sl.level; i < newNodeLevel; i++ {
			update[i] = sl.head // New levels start from head
		}
		sl.level = newNodeLevel // Update the list's current highest level
	}

	// Create the new node
	newNode := newNode(newNodeLevel, key, value)

	// Splice the new node into the list at all its levels
	for i := 0; i < newNodeLevel; i++ {
		newNode.forward[i] = update[i].forward[i] // New node points to what predecessor pointed to
		update[i].forward[i] = newNode            // Predecessor points to the new node
	}

	sl.length++ // Increment list length
}

// Delete removes an element with the given key.
// Returns true if the element was found and deleted, false otherwise.
func (sl *SkipList) Delete(key float64) bool {
	sl.mutex.Lock() // Full lock for deletion
	defer sl.mutex.Unlock()

	// update slice stores pointers to the nodes that precede the node to be deleted.
	update := make([]*Node, sl.maxLevel)
	node := sl.head

	// Find predecessors of the node to delete
	for i := sl.level - 1; i >= 0; i-- {
		for node.forward[i] != nil && node.forward[i].key < key {
			node = node.forward[i]
		}
		update[i] = node // Store predecessor at level i
	}

	// Candidate node to delete (at base level)
	nodeToDelete := node.forward[0]

	// Check if the node exists and the key matches
	if nodeToDelete == nil || nodeToDelete.key != key {
		return false // Key not found
	}

	// Bypass the nodeToDelete at all levels it exists in
	for i := 0; i < sl.level; i++ {
		// If the predecessor at this level points to the nodeToDelete...
		if update[i].forward[i] == nodeToDelete {
			// ...make the predecessor point to the node *after* nodeToDelete
			update[i].forward[i] = nodeToDelete.forward[i]
		}
	}

	// After removing the node, check if the highest levels became empty
	// and decrease the list's level accordingly.
	for sl.level > 1 && sl.head.forward[sl.level-1] == nil {
		sl.level--
	}

	sl.length-- // Decrement list length
	return true
}

// Len returns the number of elements in the skip list.
func (sl *SkipList) Len() int {
	sl.mutex.RLock()
	defer sl.mutex.RUnlock()
	return sl.length
}

// PrintList is a utility function to visualize the skip list (for debugging).
func (sl *SkipList) PrintList() {
	sl.mutex.RLock()
	defer sl.mutex.RUnlock()

	fmt.Println("\nSkip List Structure:")
	fmt.Printf("Current Level: %d, Length: %d\n", sl.level, sl.length)
	for i := sl.level - 1; i >= 0; i-- {
		fmt.Printf("Level %d: head -> ", i)
		node := sl.head.forward[i]
		count := 0
		for node != nil {
			fmt.Printf("[%v:%v] -> ", node.key, node.value)
			node = node.forward[i]
			count++
			if count > sl.length+5 { // Safety break for potential cycles (shouldn't happen)
				fmt.Print("... (possible cycle or too long)")
				break
			}
		}
		fmt.Println("nil")
	}
	fmt.Println("--- End Skip List ---")
}
